1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| #include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <stack>
using namespace std;
const int maxn = 2e5 + 5;
struct E{
int to, nxt;
}e[maxn << 1];
int head[maxn], tot = 1;
void addedge(int u, int v){
e[++tot].to = v, e[tot].nxt = head[u];
head[u] = tot;
}
int n, m, Q, u[maxn], v[maxn];
int dfn[maxn], low[maxn], tdx = 0;
int col[maxn], Ctot = 0, Ttot = 0; bool ins[maxn];
stack <int> s; int rt[maxn];
void Tarjan(int cur, int pre){
rt[cur] = Ttot;
dfn[cur] = low[cur] = ++tdx;
s.push(cur); ins[cur] = 1;
for (int i = head[cur]; i; i = e[i].nxt){
if ((i ^ 1) == pre) continue;
int v = e[i].to;
if (dfn[v] == 0) Tarjan(v, i), low[cur] = min(low[cur], low[v]);
else if (ins[v]) low[cur] = min(low[cur], low[v]);
}
if (low[cur] == dfn[cur]){
++Ctot;
while (s.top() != cur){
int tmp = s.top(); s.pop();
col[tmp] = Ctot;
ins[tmp] = 0;
}
col[cur] = Ctot; ins[cur] = 0; s.pop();
}
}
int dep[maxn], f[maxn][25];
void dfs1(int cur, int fa){
f[cur][0] = fa; dep[cur] = dep[fa] + 1;
for (int i = 1; (1 << i) <= dep[cur]; i++)
f[cur][i] = f[f[cur][i - 1]][i - 1];
for (int i = head[cur]; i; i = e[i].nxt)
if (e[i].to != fa) dfs1(e[i].to, cur);
}
int LCA(int u, int v){
if (dep[u] > dep[v]) swap(u, v);
for (int i = 20; i >= 0; i--)
if (dep[v] - (1 << i) >= dep[u]) v = f[v][i];
if (u == v) return u;
for (int i = 20; i >= 0; i--)
if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
return f[u][0];
}
int tg[2][maxn];
void dfs2(int cur, int fa){
for (int i = head[cur]; i; i = e[i].nxt){
int v = e[i].to;
if (v == fa) continue;
dfs2(v, cur);
tg[0][cur] += tg[0][v];
tg[1][cur] += tg[1][v];
}
if (tg[0][cur] > 0 && tg[1][cur] > 0){
puts("No"); exit(0);
}
}
int main(){
scanf("%d%d%d", &n, &m, &Q);
for (int i = 1; i <= m; i++){
scanf("%d%d", u + i, v + i);
addedge(u[i], v[i]);
addedge(v[i], u[i]);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) ++Ttot, Tarjan(i, 0);
memset(e, 0, sizeof e); memset(head, 0, sizeof head); tot = 1;
for (int i = 1; i <= m; i++)
if (col[u[i]] != col[v[i]]) addedge(col[u[i]], col[v[i]]), addedge(col[v[i]], col[u[i]]);
dfs1(1, 0);
for (int qu, qv, i = 1; i <= Q; i++){
scanf("%d%d", &qu, &qv);
if (rt[qu] != rt[qv]){
puts("No"); return 0;
}
qu = col[qu], qv = col[qv];
int lca = LCA(qu, qv);
tg[0][qu]++, tg[0][lca]--;
tg[1][qv]++, tg[1][lca]--;
} dfs2(1, 0);
puts("Yes");
return 0;
}
|